By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 37, Issue 3, pp. 671-976

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Effective Strong Dimension in Algorithmic Information and Computational Complexity

Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo

pp. 671-705

BibTeX  Abstract Full Text:  PDF

New Approaches for Virtual Private Network Design

Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, and Martin Skutella

pp. 706-721

BibTeX  Abstract Full Text:  PDF

The Time-Complexity of Local Decision in Distributed Agreement

Partha Dutta, Rachid Guerraoui, and Bastian Pochon

pp. 722-756

BibTeX  Abstract Full Text:  PDF

A Nearly Linear-Time Approximation Scheme for the Euclidean $k$-Median Problem

Stavros G. Kolliopoulos and Satish Rao

pp. 757-782

BibTeX  Abstract Full Text:  PDF

Hamming Codes, Hypercube Embeddings, and Fault Tolerance

William Aiello and F. T. Leighton

pp. 783-803

BibTeX  Abstract Full Text:  PDF

Planar Earthmover Is Not in $L_1$

Assaf Naor and Gideon Schechtman

pp. 804-826

BibTeX  Abstract Full Text:  PDF

Learning Monotone Decision Trees in Polynomial Time

Ryan O'Donnell and Rocco A. Servedio

pp. 827-844

BibTeX  Abstract Full Text:  PDF

Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

Paul Beame, Toniann Pitassi, and Nathan Segerlind

pp. 845-869

BibTeX  Abstract Full Text:  PDF

Improved Bounds on Nonblocking 3-Stage Clos Networks

José R. Correa and Michel X. Goemans

pp. 870-894

BibTeX  Abstract Full Text:  PDF

The Resolution Complexity of Random Constraint Satisfaction Problems

Michael Molloy and Mohammad R. Salavatipour

pp. 895-922

BibTeX  Abstract Full Text:  PDF

A Min-Max Theorem on Tournaments

Xujin Chen, Xiaodong Hu, and Wenan Zang

pp. 923-937

BibTeX  Abstract Full Text:  PDF

The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts

Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard J. Schulman

pp. 938-958

BibTeX  Abstract Full Text:  PDF

Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs

Noga Alon, Eldar Fischer, and Ilan Newman

pp. 959-976

BibTeX  Abstract Full Text:  PDF